package com.study.algorithm.niuke.practice;


/**
 * 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，
 * 每一次只能向左，右，上，下四个方向移动一格，
 * 但是不能进入行坐标和列坐标的数位之和大于k的格子。
 * 例如，当k为18时，机器人能够进入方格（35,37），
 * 因为3+5+3+7 = 18。但是，它不能进入方格（35,38），
 * 因为3+5+3+8 = 19。请问该机器人能够达到多少个格子
 * <p>
 * <p>
 * 我是使用深度遍历做的
 */
public class MovingCount {

    private static final int top = 0;
    private static final int right = 1;
    private static final int foot = 2;
    private static final int left = 3;

    public int movingCount(int threshold, int rows, int cols) {
        if (threshold <= 0 || rows <= 0 || cols <= 0) {
            return 0;
        }

        int[][] visited = new int[rows][cols];
        int visitedCount = 1;
        visited[0][0] = 1;
        visitedCount += searchNext(threshold, visited, right, 0, 0, rows, cols);
        visitedCount += searchNext(threshold, visited, foot, 0, 0, rows, cols);
        return visitedCount;
    }


    private boolean outOfEdge(int currRow, int currCol, int rows, int cols) {
        return !(currRow > -1 && currRow < rows && currCol > -1 && currCol < cols);
    }

    private int searchNext(int threshold, int[][] visited, int direction, int row, int col, int rows, int cols) {
        int visitCount = 0;
        int currRow = row;
        int currCol = col;
        if (direction == top) {
            currRow = row - 1;

        }
        if (direction == right) {
            currCol = col + 1;
        }

        if (direction == foot) {
            currRow = row + 1;
        }
        if (direction == left) {
            currCol = col - 1;
        }

        if (outOfEdge(currRow, currCol, rows, cols)
                || !isReachableForCurrDirection(threshold, currRow, currCol)) {
            return visitCount;
        }
        int isVisited = visited[currRow][currCol];
        if (isVisited == 1) {
            return 0;
        }
        visited[currRow][currCol] = 1;
        visitCount = 1;
        visitCount += searchNext(threshold, visited, top, currRow, currCol, rows, cols);
        visitCount += searchNext(threshold, visited, right, currRow, currCol, rows, cols);
        visitCount += searchNext(threshold, visited, foot, currRow, currCol, rows, cols);
        visitCount += searchNext(threshold, visited, left, currRow, currCol, rows, cols);
        return visitCount;
    }

    public boolean isReachableForCurrDirection(int threshold, int currRow, int currCol) {
        return sumDigit(currRow) + sumDigit(currCol) <= threshold;
    }

    public int sumDigit(int n) {
        int total = 0;
        while (n > 0) {
            total += n % 10;
            n = n / 10;
        }
        return total;
    }


}
